perm filename T3[144,DBL] blob
sn#026387 filedate 1973-02-26 generic text, type T, neo UTF8
00100 BLANKS ORIG *+24 ;These locs. should always be blank.
00200 N CON 0 ;The number of nodes
00300 TPL ORIG *+24 ;The desired total path length
00400 LOG CON 0 ;A sequential linear list, whose i th element
00500 * is Floor(log(i)), where log ≡ (log to base 2).
00600 ORIG *+500 ;I have assumed that n will never be > 500.
00700 S CON 0 ;A sequential linear list whose i th element
00800 * is the sum of elements 1 to i of LOG.
00900 ORIG *+500
01000 ORIG *+500
01005 LOOKUP ORIG *+500
01100 BAL ORIG *+500
01200 ZEROS EQU 3500 ;An area which remains as zeros.
01300 VISIT EQU 1:1 ;The field spec. indicating whether or not wehave visited this node yet.
01400 BUFFER ORIG *+800 ;This should be ample to hold a finaltree traversal encoding.
01500 DIFF CON 0 ;Holds the difference between the pure balanced+
01600 * tail tree path length, and the desired TPL.
01700 XOLD CON 0 ;Holds the previous path length, in case we went too far.
01800 K CON 0 ;Holds the number of nodes in the balanced part oftree.
01900 TITLE ALF N
02000 ALF TPL
02100 ALF
02200 ALF
02300 ALF
02400 ALF Doug
02500 ALF Lenat
02600 ALF
02700 ALF CS 14
02800 ALF 4A P
02900 ALF roble
03000 ALF m 4
03100 ALF
03200 ALF Total
03300 ALF Path
03400 ALF Leng
03500 ALF th in
03600 ALF Bina
03700 ALF ry Tr
03800 ALF ees
03900 ORIG *+5
04000 RSON EQU 4:4 ;Field in a TREE node pointing to right son.
04100 LSON EQU 5:5 ;Field specification pointing to the left son.
04200 * note that this restricts n to be under 65; a trivial modification
04300 * will allow n to range up to 500.If n is requested over 2000, a
04400 * total revision of the program would be necessary.
04500 SONS EQU 4:5 ;Field which is blank iff the node is a leaf.
04600 FATHER EQU 3:3 ;Field spec. pointing to the node's parent.
04700 FIELD EQU 4:4 ;Field spec. for the field byte of a MIX instruction.
04800 LPAREN EQU 42
04900 RPAREN EQU 43
05000 STAR EQU 46
05100 READER EQU 16
05200 PRINTER EQU 18
05300 *
05400 *
05500 CONTINU OUT BLANKS(PRINTER)
05600 OUT BLANKS(PRINTER)
05700 START IN N(READER) ;Read n. We are permitted the inefficiency of
05800 JBUS *(READER) ;JBUS instructions. See Knuth and
05900 * my earlier programs for examples
06000 * of more efficient I/O.
06100 LDX N
06200 JXNZ *+2 ;Are we finished the final problem in the run??
06300 HLT ; yes; so we halt.
06400 OUT TITLE(PRINTER) ; Here we
06500 * write out a title line.
06600 OUT N(PRINTER) ;We write n and tpl
06700 JBUS *(PRINTER) ; while they are still in char. form.
06800 ENTA 0
06900 NUM
07000 STA N ; re-store the numeric value of n.
07100 LDX TPL ;Convert TPL from char. code to numeric.
07200 ENTA 0
07300 NUM
07400 STA TPL
07500 ENT1 TREE
07600 LD2 N
07700 ST2 *+1(FIELD)
07800 MOVE ZEROS ;WARNING: INSTRUCTION MODIFICATION HERE.
07900 *
08000 *
08100 * The following loop sets up the first n entries in LOG and in S:
08200 *
08300 ENT1 0 ;rI1 holds the exponent of the current power of 2.
08400 ENT2 0 ;rI2 holds the sum of all previous terms.
08500 ENT3 1 ;rI3 holds 2 to the current power( 2 ↑ <rI1> ).
08600 ENT4 0 ;rI4 stops us when n terms have been computed.
08700 ENTA 1 ;rA tells us when to increase the terms of LOG.
08800 *
08900 JMP LOOP1 ;A standard programming trick, saving n-1 tyme units.
09000 SKIP1 INC3 0,3 ;Double rI3; i.e, increaase its log by 1.
09100 ENTA 0,3 ;rA tells us when to increase the terms of LOG.
09200 INC1 1
09300 LOOP1 INC2 0,1
09400 INC4 1
09500 ST2 S,4
09600 ST1 LOG,4
09700 DECA 1
09800 JAP LOOP1
09900 CMP4 N
10000 JLE SKIP1
10100 *
10200 *
10300 *
10400 *
10500 * This loop is the "guts" of the program: we determine how many nodes
10600 * are in the balanced section, and how many are in the tail.
10700 *
10800 ENT3 0 ;rI3 holds the L*(L+1)/2 term.
10900 LD5 N ;rI5 holds K, the number of nodes in the balanced part.
11000 ENT6 -1 ;rI6 holds L, the number of nodes in the tail.
11100 DEC5 0,6 ;K must always remain equal to N - L.
11200 LOOP2 INC6 1
11300 DEC5 1
11400 INC3 0,6 ;Update this term.
11500 STA XOLD
11600 ENTA 0,6 ;Get the L * Floor(log(k)) term.
11700 MUL LOG,5
11800 SLAX 5
11900 INCA 0,3 ;The accumulator now contains the sum of terms 1,2.
12000 ADD S,5 ;We add in the sum of LOGs from 1 to K: the final term.
12100 CMPA TPL ;See if we have gone far enough....
12200 JL LOOP2 ; we haven't; go back and try again.
12300 * WE HAVE SUCCEEDED !!!
12400 *
12500 LDA TPL
12600 SUB XOLD
12700 STA DIFF
12800 INC5 1
12900 DEC6 1
13000 ENT2 0,5
13100 *
13200 *
13300 *
13400 ST5 K
13500 LD4 LOG,K
13600 INC4 1
13700 ENTA LPAREN
13800 ENTX RPAREN
13900 ENT2 STAR
14000 ENT1 BAL+4
14200 ENT4 0
14300 *
14400 LD3N N
14500 LOOP8 STA BAL,3
14600 INC3 1
14700 J3N LOOP8
14800 *
14900 ENT3 2
15000 *
15100 LOOP9 STX BAL,3
15200 ST2 BAL+1,3
15300 ST3 LOOKUP,4
15400 STA BAL+2,3
15500 ST3 *+1(FIELD)
15600 MOVE BAL,4
15700 INC3 5,3
15800 DEC4 1
15900 DEC4 1
16000 J4P LOOP9
16100 *
16200 ENT4 0
16300 LD3 LOG-1,5
16400 INC3 0,6
16500 *
16600 LOOP10 STA BUFFER,4
16700 INC4 1
16800 DEC3 1
16900 J3P LOOP10
17000 *
17100 LD1N DIFF
17200 INC1 0,6
17300 ENT3 1,6
17400 *
17500 LOOP11 ST2 BUFFER,4
17600 STX BUFFER+1,4
17700 INC4 2
17800 J1NZ L11B
17900 ST2 BUFFER,4
18000 STA BUFFER+1,4
18100 ST2 BUFFER+2,4
18200 STX BUFFER+3,4
18300 STX BUFFER+4,4
18400 INC4 5
18500 L11B DEC1 1
18600 DEC3 1
18700 J3NN LOOP11
18800 *
18900 LD6N K
19000 LD1 LOOKUP,6
19100 ENT5 -6,1
19200 ENT1 BUFFER,4
19300 ST5 *+1(FIELD)
19400 MOVE BAL+7
19500 INC4 0,5
19600 LD5 N
19700 LD5 LOG-1,5
19800 DEC5 2
19900 LOOP12 STX BUFFER,4
20000 INC4 1
20100 DEC5 1
20200 J5P LOOP12
20300 *
24900 * Here we do the actual printing of the encoded traversal
25000 *
25100 ENT3 0
25200 LOOP13 OUT BUFFER,3(PRINTER)
25300 INC3 24
25400 DEC4 24
25500 J4NN LOOP13
25600 *
25700 * Go back and read in a new request
25800 *
25900 JMP CONTINU ;This differs from START only in the printing out of 2 blank lines.
26000 *
26100 END START